/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
// 暴力查找，超时
var searchMatrix = function (matrix, target) {
  const xlen = matrix.length;
  for (let i = 0; i < xlen; i++) {
    if (matrix[i].includes(target)) {
      return true;
    }
  }

  return false;
};

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
/* 
为了在满足特定条件的二维矩阵中高效搜索目标值，可以将二维矩阵映射为一维数组，
然后使用二分查找。这种方法的时间复杂度为 O (log (mn))，其中 m 和 n 分别是矩阵的行数和列数。

方法思路
二维矩阵映射：将二维矩阵视为一维数组，其中每个元素的位置可以通过行和列的索引计算得到。
例如，矩阵中第 i 行第 j 列的元素对应一维数组中的索引为i * n + j，其中 n 是矩阵的列数。
二分查找：在映射后的一维数组上执行二分查找。计算中间索引对应的行和列，比较中间元素与目标值的大小，然后根据比较结果调整搜索范围。
*/
var searchMatrix = function (matrix, target) {
  const m = matrix.length;
  if (m === 0) return false;
  const n = matrix[0].length;

  let left = 0;
  let right = m * n - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midValue = matrix[Math.floor(mid / n)][mid % n];

    if (midValue === target) {
      return true;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
};